package top.truism.stack;

import java.util.LinkedList;

/**
 * 矩阵中滑动窗口中的最大值数组
 */
public class MaxValueInWindow {

    /**
     * @param arr 一维矩阵元素
     * @param w   窗口的大小
     * @return
     */
    public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || arr.length < w) {
            return null;
        }
        LinkedList<Integer> list = new LinkedList<>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            // 队列末尾始终保存当前窗口最大值的索引
            while (!list.isEmpty() && arr[list.peekLast()] <= arr[i]) {
                list.pollLast();
            }
            list.addLast(i);

            // 当前下标已落后窗口左边界
            if (list.peekFirst() == i - w) {
                list.pollFirst();
            }
            if (i >= w - 1) {
                res[index++] = arr[list.peekFirst()];
            }
        }
        return res;
    }

}
